package com.zyk.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 糖果是要平分的, 分给弟弟和妹妹.
 * 怎么分使得妹妹获得的糖果种类最大. 返回可获得的糖果种类
 * @author zhangsan
 * @date 2021/4/30 14:54
 */
public class C575 {

    // 1. 使用set, 时间复杂度一次遍历O(N)
    public static int distributeCandies(int[] candyType) {
        Set<Integer> set = new HashSet<>();
        for (int candy : candyType) {
            set.add(candy);
        }
        return Math.min(candyType.length >> 1, set.size());
    }

    // 2. 排序 + 统计 O(n*logN) + O(n)   即 O(n*logn)
    public static int distributeCandies2(int[] candies) {
        Arrays.sort(candies);
        int count = 1;
        for (int i = 1; i < candies.length && count < candies.length / 2; i++)
            if (candies[i] > candies[i - 1])
                count++;
        return count;
    }


    // for test
    public static void main(String[] args) {

    }

}
